#include <iostream>

struct Tnode
{
  std::string word;
  std::size_t count;
  Tnode* left;
  Tnode* right;
};


void
print_tree(Tnode* node)
{
  if ((node->left == NULL) && (node->right == NULL))
    {
      std::cerr << node->word << ", " << node->count << std::endl;
    }
  else
    {
      if (node->left != NULL)
	{
	  print_tree(node->left);
	}

      std::cerr << node->word << ", " << node->count << std::endl;

      if (node->right != NULL)
	{
	  print_tree(node->right);
	}
    }
}


void
add_word(Tnode* node, char* word)
{
  int cmp = strcmp(node->word.c_str(), word);

  if (cmp == 0)
    {
      node->count++;
    }
  else if (cmp > 0) // branch to the left
    {
      if (node->left == NULL)
	{
	  Tnode* l = new Tnode();
	  l->word = word;
	  l->count = 1;
	  node->left = l;
	}
      else
	{
	  add_word(node->left, word);
	}
    }
  else // branch to the right
    {
      if (node->right == NULL)
	{
	  Tnode* r = new Tnode();
	  r->word = word;
	  r->count = 1;
	  node->right = r;
	}
      else
	{
	  add_word(node->right, word);
	}
    }
}

Tnode*
create_tree(char* words[], std::size_t n)
{
  Tnode* root = new Tnode();
  root->word = words[0];
  root->count = 1;

  for (std::size_t i = 1; i < n; ++i)
    {
      add_word(root, words[i]);
    }
  
  return root;
}


int
main()
{
  char* words[] = {"one", "two", "one", "three", "four"};
  Tnode* tree = create_tree(words, 5);
  print_tree(tree);
}
